//合并K个升序链表
//https://leetcode.cn/problems/merge-k-sorted-lists/submissions/


//n代表节点个数

//借助vector - O(n)/O(n)
//class Solution {
//public:
//    ListNode* mergeKLists(vector<ListNode*>& lists) {
//        if (lists.size() == 0) return nullptr;
//        else if (lists.size() == 1) return lists[0];
//        //默认合并到第一个链表中 - 保证必须有2条链
//        vector<int> v;
//        for (const auto& l : lists)
//        {
//            ListNode* cur = l;
//            while (cur)
//            {
//                v.push_back(cur->val);
//                cur = cur->next;
//            }
//        }
//        sort(v.begin(), v.end());
//        ListNode* head = nullptr;
//        ListNode* tail = nullptr;
//        for (const auto& n : v)
//        {
//            if (!head)
//            {
//                head = tail = new ListNode(n);
//            }
//            else
//            {
//                tail->next = new ListNode(n);
//                tail = tail->next;
//            }
//        }
//        return head;
//    }
//};


//归并排序 - O(n)/O(1)
// class Solution {
//     ListNode* mergo(ListNode* l1,ListNode* l2)
//     {
//         if(!l1) return l2;
//         if(!l2) return l1;

//         ListNode* newhead = new ListNode(-1);
//         ListNode* cur = newhead;
//         while(l1 && l2)
//         {
//             if(l1->val <= l2->val)
//             {
//                 cur->next = l1;
//                 l1 = l1->next;
//             }
//             else
//             {
//                 cur->next = l2;
//                 l2 = l2->next;
//             }
//             cur = cur->next;
//         }
//         if(l1) cur->next = l1;
//         else if(l2) cur->next = l2;
//         cur = newhead->next;
//         delete newhead;
//         return cur;
//     }
// public:
//     ListNode* mergeKLists(vector<ListNode*>& lists) {
//         if(lists.size() == 0) return nullptr;
//         if(lists.size() == 1) return lists.front();
//         int n = lists.size();
//         ListNode* cur = mergo(lists[0],lists[1]);
//         for(int i = 2;i<n;++i) cur = mergo(cur,lists[i]);
//         return cur;
//     }
// };


//优先级队列 - O(n)/O(N) N代表lists个数
// class Solution {
//     struct compare
//     {
//         bool operator()(ListNode* l1,ListNode*l2) 
//         {
//             return l1->val > l2->val;
//         }
//     };
// public:
//     ListNode* mergeKLists(vector<ListNode*>& lists) {
//         priority_queue<ListNode*,vector<ListNode*>,compare> pq;
//         for(ListNode* l:lists) if(l) pq.push(l);

//         ListNode* newhead = new ListNode(-1);
//         ListNode* cur = newhead;
//         while(!pq.empty())
//         {
//             ListNode* l = pq.top(); pq.pop();
//             cur->next = l;
//             cur = cur->next;
//             if(l->next) pq.push(l->next);
//         }
//         cur = newhead->next;
//         delete newhead;
//         return cur;
//     }
// };
